package leetcode.N101_N200;

import java.util.ArrayList;
import java.util.List;

public class N155 {

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(2147483646);
        minStack.push(2147483646);
        minStack.push(2147483647);
        minStack.top();
        minStack.pop();
        minStack.getMin();
        minStack.pop();
        minStack.getMin();
        minStack.pop();
        minStack.push(2147483647);
        minStack.top();
        minStack.getMin();
        minStack.push(-2147483648);
        minStack.top();
        minStack.getMin();
        minStack.pop();
        minStack.getMin();
    }

}


class MinStack {
    int index;
    List<Integer> elements;
    List<Integer> minIndex;

    /** initialize your data structure here. */
    public MinStack() {
        this.index = -1;
        this.elements = new ArrayList<>();
        this.minIndex = new ArrayList<>();
    }

    public void push(int x) {
        if (index == -1) {
            // 当前没有元素
            index = 0;
            elements.add(index, x);
            minIndex.add(index, index);
            return;
        }
        // 获取当前的最小值
        int min = getMin();
        // 把元素放到对应的位置 并且index是指向当前元素所在的下表位
        elements.add(++index, x);
        if (x < min) {
            // 如果x小于最小值 则当前版本的最小值保存当前值
            minIndex.add(index, index);
        } else {
            // 如果x不小于最小值 则当前版本的最小值继续使用之前的版本最小值
            minIndex.add(index, minIndex.get(index - 1));
        }
    }

    public void pop() {
        if (index == -1) {
            return;
        }
        index--;
    }

    public int top() {
        return elements.get(index);
    }

    public int getMin() {
        return elements.get(minIndex.get(index));
    }
}
